#include <functional>
#include <iostream>
#include <vector>

template <typename T>
void print(const std::vector<std::vector<T>>& vecs) {
    for (auto v : vecs) {
        for (auto n : v) {
            std::cout << n << ", ";
        }
        std::cout << '\n';
    }
    std::cout << '\n';
}

class Solution {
  public:
    int uniquePathsWithObstacles_dp(std::vector<std::vector<int>>& obstacleGrid) {
        if (obstacleGrid.size() == 0) return 0;
        std::vector<std::vector<int>> memo(obstacleGrid.size(), std::vector<int>(obstacleGrid[0].size(), -1));
        memo[obstacleGrid.size() - 1][obstacleGrid[0].size() - 1] = 1;
        std::function<int(int, int)> helper;
        helper = [&](int x, int y) -> int {
            // 因为可能有障碍， 所以是 and
            if (obstacleGrid[x][y] == 1) return 0;
            if (memo[x][y] == -1) {
                int tmp1 = 0, tmp2 = 0;
                if (y + 1 < obstacleGrid[0].size()) tmp1 = helper(x, y + 1);
                if (x + 1 < obstacleGrid.size()) tmp2 = helper(x + 1, y);
                memo[x][y] = tmp1 + tmp2;
            }
            return memo[x][y];
        };
        return helper(0, 0);
    }

    int uniquePathsIII(std::vector<std::vector<int>>& grid) {
        if (grid.size() == 0) return 0;
        std::function<int(int, int)> helper;
        int walked = 0;
        int point_nums = grid.size() * grid[0].size() - 1;  // need process
        helper = [&](int x, int y) -> int {
            // std::cout << walked << ", " << point_nums << '\n';
            // print(grid);
            if (grid[x][y] == -1) return 0;
            if (grid[x][y] == 2) {
                if (walked == point_nums)
                    return 1;
                else
                    return 0;
            }
            grid[x][y] = 7;
            ++walked;
            int up = 0, down = 0, left = 0, right = 0;
            if (x + 1 < grid.size() and grid[x + 1][y] != 7) right = helper(x + 1, y);
            if (y + 1 < grid[0].size() and grid[x][y + 1] != 7) down = helper(x, y + 1);
            if (x - 1 >= 0 and grid[x - 1][y] != 7) left = helper(x - 1, y);
            if (y - 1 >= 0 and grid[x][y - 1] != 7) up = helper(x, y - 1);
            --walked;  // 回溯
            grid[x][y] = 0;
            return up + down + left + right;
        };
        int x = 0, y = 0;
        for (int i = 0; i < grid.size(); ++i) {
            for (int j = 0; j < grid[0].size(); ++j) {
                if (grid[i][j] == 1) x = i, y = j;
                if (grid[i][j] == -1) --point_nums;
            }
        }
        return helper(x, y);
    }
};

int main() {
    // std::vector<std::vector<int>> grid{{1, 0, 0, 0}, {0, 0, 0, 0}, {0, 0, 2, -1}};
    std::vector<std::vector<int>> grid{{1, 2}};
    Solution s;
    std::cout << s.uniquePathsIII(grid) << '\n';
    return 0;
}
